package com.example.question.dp.dp4;

/**
 * @Date 2023-07-30
 * @Author Jonathan
 */
public class Code08_152 {
    public static void main(String[] args) {
        Code08_152 code = new Code08_152();
//        int i = code.maxProduct(new int[]{-2, 4, -3});
//        int i = code.maxProduct(new int[]{-2, 3, -2, 4});
        System.out.println("code.maxProduct(new int[]{-1, -2, -9, -6}) = " + code.maxProduct(new int[]{-1, -2, -9, -6}));

    }

    // [2,3,-2,4]
    //  2 6 -2 4
    // [-2,3,-4]
    public int maxProduct1(int[] nums) {
        int m = nums.length;
        int pre = 0;
        int maxProduct = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = i; j < m; j++) {
                if (j == i) {
                    pre = nums[i];
                } else {
                    pre = pre * nums[j];
                }
                maxProduct = Math.max(maxProduct, pre);
            }
        }
        return maxProduct;
    }

    public int maxProduct(int[] nums) {
        int m = nums.length;
        int[] maxDp = new int[m];
        int[] minDp = new int[m];
        minDp[0] = maxDp[0] = nums[0];
        int maxProduct = nums[0];
        for (int i = 1; i < m; i++) {
            maxDp[i] = Math.max(maxDp[i - 1] * nums[i], Math.max(nums[i], minDp[i - 1] * nums[i]));
            minDp[i] = Math.min(minDp[i - 1] * nums[i], Math.min(nums[i], maxDp[i - 1] * nums[i]));
            maxProduct = Math.max(maxDp[i], maxProduct);
        }
        return maxProduct;
    }
}
